/*
题目：排序数组
给你一个整数数组 nums，请你将该数组升序排列。
https://leetcode.cn/problems/sort-an-array/
 */
public class SortArray {
    public int[] sortArray(int[] nums) {
        countSort(nums);
        return nums;
    }

    //计数排序
    private void countSort(int[] nums) {
        int maxVal = nums[0];
        int minVal = nums[0];
        for (int x : nums) {
            if (x > maxVal) {
                maxVal = x;
            }
            if (x < minVal) {
                minVal = x;
            }
        }

        int[] table = new int[maxVal - minVal + 1];
        for (int x : nums) {
            table[x - minVal]++;
        }

        int index = 0;
        for (int i = 0; i < table.length; i++) {
            while (table[i] > 0) {
                nums[index++] = i + minVal;
                table[i]--;
            }
        }
    }

    //堆排序
    private void heapSort(int[] nums) {
        //先构建大根堆，再从最后一个双亲结点开始向下调整
        for (int i = (nums.length - 2) / 2; i >= 0; i--) {
            shiftDown(nums, i, nums.length);
        }

        //然后把第一个和最后一个节点交换，再向下调整
        int lastElem = nums.length - 1; //最后一个元素下标
        while (lastElem > 0) {
            swap(nums, 0, lastElem);
            shiftDown(nums, 0, lastElem--);
        }

    }

    private void shiftDown(int[] nums, int parent, int end) {
        int child = parent * 2 + 1;

        while (child < end) {
            if (child + 1 < end && nums[child] < nums[child + 1]) {
                child++;
            }
            if (nums[child] > nums[parent]) {
                swap(nums, child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break; //否则就已经是大根堆了
            }
        }
    }

    //归并排序
    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) {
            return ;
        }
        int mid = left + ((right - left) >>> 1);
        //先分
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        merge(nums, left, mid, right);
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int start1 = left;
        int start2 = mid + 1;

        int[] tmpArr = new int[right - left + 1];
        int index = 0;
        while (start1 <= mid && start2 <= right) {
            if (nums[start1] <= nums[start2]) {
                tmpArr[index++] = nums[start1++];
            } else {
                tmpArr[index++] = nums[start2++];
            }
        }
        while (start1 <= mid) {
            tmpArr[index++] = nums[start1++];
        }
        while (start2 <= mid) {
            tmpArr[index++] = nums[start2++];
        }

        for (int i = 0; i < index; i++) {
            nums[i + left] = tmpArr[i];
        }
    }

    private int[] bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {  //i 表示趟数
            boolean flg = true;
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    flg = false;
                }
            }
            if (flg) {
                break;
            }
        }

        return nums;
    }

    //希尔排序
    private int[] shellSort(int[] nums) {
        int gap = nums.length;
        while (gap > 0) {
            gap /= 2;

            //注意这里是i++
            for (int i = gap; i < nums.length; i++) {
                int j = i - gap;
                int hole = nums[i];
                for (; j >= 0; j -= gap) {
                    if (nums[j] > hole) {
                        nums[j + gap] = nums[j];
                    } else {
                        break;
                    }
                }
                nums[j + gap] = hole;
            }
        }

        return nums;
    }

    //插入排序
    private int[] insertSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int j = i - 1;
            int hole = nums[i];
            for (; j >= 0; j--) {
                if (hole < nums[j]) {
                    nums[j + 1] = nums[j];
                } else {
                    break;
                }
            }
            nums[j + 1] = hole;
        }

        return nums;
    }

    private void swap(int[] nums, int child, int parent) {
        int tmp = nums[child];
        nums[child] = nums[parent];
        nums[parent] = tmp;
    }
}
